#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 5

#define MAX(a,b) (a)>(b)?(a):(b)

void print_arrat(int A[], int n)
{
  int i;
  for(i=0;i<n;i++)
   printf("%d\t",A[i]);
   
   printf("\n"); 
}

void swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp; 
}

int partition(int A[], int start, int end)
{
  int x = A[end];
  int i = start-1;
  int j = start;
  
  for(;j<end;j++)
   {
     if(A[j]<x)
      {
        i++;
        swap(A+i, A+j); 
      } 
   } 
   swap(A+i+1, A+end);
   
   return i+1; 
}

void quick_sort(int A[], int start, int end)
{
  if(start<end)
   {
     int q = partition(A, start, end);
     quick_sort(A, start, q-1);
     quick_sort(A, q+1, end); 
   } 
}

int count_mid_n(int A[],int a_start,int a_end,int B[],int b_start,int b_end)
{
  int ret = 0; 
  if((a_start==a_end)||(b_start==b_end))
  {
    printf("min %d %d\n", A[a_start], B[b_start]);
    ret = MAX(A[a_start], B[b_start]);
    printf("ret is %d\n", ret);
    return ret;
  }
  else
  { 
   int a_mid = (a_start+a_end)/2;
   int b_mid = (b_start+b_end)/2;
   printf("a_mid is %d, b_mid is %d\n", A[a_mid], B[b_mid]);
  
   if(A[a_mid]>B[b_mid])
     return count_mid_n(A, a_start,a_mid,B,b_mid,b_end); 
   else if(A[a_mid]<B[b_mid])
     return count_mid_n(A, a_mid,a_end,B,b_start,b_mid); 
   else
     {
       ret = A[a_mid];
       return ret;
     }
   }
}

int main(int argc, char *argv[])
{
  int i;
  int ret;
  srand((unsigned int)time(NULL));
  int A[N] = {1, 2, 3, 6, 7};
  int B[N] = {0, 4, 5, 8, 9};
  
#if 0
  for(i=0;i<N;i++)
   A[i] = rand()%100;
  
  for(i=0;i<N;i++)
   B[i] = rand()%100;
  
  quick_sort(A, 0, N-1);
  quick_sort(B, 0, N-1);
  
  printf("array A is:\n");
  print_arrat(A,N);
  printf("array B is:\n");
  print_arrat(B,N);
#endif

  
  
  ret = count_mid_n(A,0,N-1,B,0,N-1); 
  printf("mid of 2n is: %d\n", ret);
  /*system("PAUSE");    */
  return 0;
}
